package com.Oct_Thirty;

/**
 * 面试题 08.03. 魔术索引
 * 魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
 *
 * 示例1:
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/magic-index-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/30 10:36
 */

public class Solution08_03 {

    //int minValue=Integer.MAX_VALUE;
    public int findMagicIndex(int[] nums) {
        return search(0,nums.length-1,nums);
    }

    //使用二分法，先检测左边的序列，要是存在最小对应值就直接返回，不用再搜索右边的序列，减少了时间
    int search(int left,int right,int[] nums){
        if (left>right) return -1;
        int mid=left+(right-left)/2;
        int index=search(left,mid-1,nums);
        if (index>-1)
        {
            return index;
        }else if (nums[mid]==mid)
        {
            return mid;
        }else
        {
            return search(mid+1,right,nums);
        }
    }

    public static void main(String[] args) {
        Solution08_03 solution08_03=new Solution08_03();
        System.out.println(solution08_03.findMagicIndex(new int[]{0, 2, 3, 4, 5}));
    }

}
